CHAPTER VIII. HIGHER CONGRUENCES. A CONGRUENCE OF DEGREE n HAS AT MOST n ROOTS IF THE MODULUS p is A PRIME. J. L, Lagrange1 proved that, if a is not divisible by the prime p, axn+bxn~1 + . . . is divisible by p for at most n integers x between p/2 and — p/2. For, let a, #, . . . , p, or be n+l such distinct integers. Then the quotient of by x — a is a polynomial axn~~l + . . . which is divisible by p when x =£,..., <r. Proceeding as before, we finally have a(p—a) divisible by p} which is impossible. L. Euler2 noted that xn— 1 is divisible by a prime p for not more than n integers x, Q<x<p. For, if x = a, is such an integer, then x — a divides xn — 1— mp, where m is a suitable integer; the quotient/ is of degree n — 1. If x = b is a second such integer, x— b divides f—m 'p. Proceeding as in algebra, we obtain the theorem stated. [The argument is applicable to any polynomial of degree ninx.] A. M. Legendre3 noted that P=(o; — a)Q-{-pA has only one more root than Q. C. F. Gauss4 proved the theorem by assuming that there is a congruence axn-\- . . .^0 (mod p) with more than n roots a, . . ., and that every congruence of degree I, Kn, has at most I roots. Substituting y+a for x, we obtain a congruence ayn+ ... =0 with more than n roots, one of which is zero. Removing the factor y, we obtain ayn"1 + . . . = 0 with more than Ti — 1 roots, contrary to hypothesis. Gauss5 noted that if a is a root of £=0 (mod p), then £ is divisible by x — a modulo p. If a, 6, . . . are incongruent roots, £ is divisible modulo p by the product (x — a)(x — 6) . . .. Hence the number of roots does not exceed the degree of £. A. Cauchy6 made the proof by use of X= (x — a)Xl (mod p), identically in x, where the degree of Xi is one less than the degree of X. A. L. Crelle7 and S. Earnshaw8 gave Lagrange 's proof. Crelle9 proved that if elt . . . , en are n distinct roots, axn+. . . = a(x — e^ . . .(x — lM6m. Ac. Berlin, 24, ann6e 1768 (1770), p. 192; Oeuvres, 2, 1868, 667-9. 2Novi Comm. Ac. Petrop., 18, 1773, p. 93; Comm. Arith., 1, 519-20. 8M6m. Ac. Roy. Sc., Paris, 1785, 466; Thdoric dcs nombres, 1798, 184. 4Disq. Arith., 1801, Art. 43. 5Posthumous paper, Wcrkc, 2, p. 217, Art. 338 (p. 214, Art. 333). Maser's Gorman translation of Gauss' Disq. Arith., etc., 1889, p. 607 (p. 604). 'Excrcices dc Math., 4, 1829, 219; Oeuvrcs, (2), 9, 261; Comptes Rendus Paris, 12, 1841, 831-2; Exerciccs d' Analyse ct de Phys. Math., 2, 1841, 1-40, Oeuvrcs, (.2), 12. 7Berlin Abhand., Math., 1832, p. 34. "Cambridge Math. Jour., 2, 1841, 79. "Berlin Abhand., Math., 1843, 50-54.